//给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 
//
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 
//
// 
//
// 例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = 
//"ABCCED"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：board = [["a","b"],["c","d"]], word = "abcd"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= board.length <= 200 
// 1 <= board[i].length <= 200 
// board 和 word 仅由大小写英文字母组成 
// 
//
// 
//
// 注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/ 
// Related Topics 数组 回溯 矩阵 👍 597 👎 0

package leetcode.editor.offer;

class JuZhenZhongDeLuJingLcof {
    public static void main(String[] args) {
        Solution solution = new JuZhenZhongDeLuJingLcof().new Solution();
        System.out.println(solution.exist(new char[][]{{'a', 'b'}}, "ba"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 剑指 Offer 12. 矩阵中的路径
    // https://blog.algomooc.com/012.html
    class Solution {
        public boolean exist(char[][] board, String word) {
            if (word == null && word.length() == 0) return true;
            char[] wordArray = word.toCharArray();
            // 每次字符都进行搜索
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    // 注意不能直接 return dfs(board, wordArray, i, j, 0);
                    // 此时这种情况只会搜索一次，而不是每个字符都搜索
                    // 所以会漏掉反序的情况
                    // [["a","b"]]
                    // "ba"
                    if (dfs(board, wordArray, i, j, 0)) return true;
                }
            }
            return false;
        }

        /**
         * 上下左右都要搜索
         *
         * @param board
         * @param word
         * @param row
         * @param col
         * @param index
         * @return
         */
        public boolean dfs(char[][] board, char[] word, int row, int col, int index) {
            // 字符和word中不相等，以及左右上下超过board的范围，此时都是返回false
            // board[row][col] != word[index]放在最后不然有数组越界问题，得先判断行和列的范围
            if (row >= board.length || row < 0 || col >= board[0].length || col < 0 || board[row][col] != word[index])
                return false;
            // 此时搜索的索引等于word，此时搜索完毕
            if (index == word.length - 1) return true;

            board[row][col] = '\0'; // 表示此位置已经搜索过且满足，前面不满足的已经返回false
            // 像下左右进行递归搜索，+1会自动回溯
            boolean isEqual =
                    dfs(board, word, row + 1, col, index + 1)  // 搜索下边
                            || dfs(board, word, row - 1, col, index + 1)    // 搜索上边
                            || dfs(board, word, row, col + 1, index + 1)    // 搜索右边
                            || dfs(board, word, row, col - 1, index + 1); // 搜索左边
            board[row][col] = word[index];  // 回溯，返回原来的字符
            return isEqual;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
